import { TreeNode, buildTree } from "../../utils/treeUtil.js"



/**236. 二叉树的最近公共祖先 */
export function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    // 后序遍历 - 判断是否是公共祖先，就看当前节点的左右子树是否包含p和q
    // 先递归，目的是从最下面开始查找，看看 当前的节点 是否是 p或q
    // 然后找到了，就会返回，交给下面的逻辑判断
    if (root === q || root === p || root === null) return root;
    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)
    //对当前节点的处理 
    //如果left 和 right都不为空，说明此时root就是最近公共节点
    if (left !== null && right !== null) return root;
    //单独一个空就返回另一个
    if (left == null && right !== null) return right;
    else if (left !== null && right == null) return left;
    else return null;//  (left == null && right == null)  
}
/**617. 合并二叉树
 * - 给你两棵二叉树： root1 和 root2 。
 * - 如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
 */
export function mergeTrees(root1: TreeNode | null = buildTree([1, 3, 2, 5]), root2: TreeNode | null = buildTree([2, 1, 3, null, 4, null, 7])): TreeNode | null {
    //哪一边为空了，剩下的节点直接让另一个树接管
    if (!root1) return root2
    if (!root2) return root1
    //用root1当容器接管
    root1.val += (root2.val || 0)
    root1.left = mergeTrees(root1.left, root2.left)
    root1.right = mergeTrees(root1.right, root2.right)
    return root1
}
/**2583. 二叉树中的第 K 大层和 */
export function kthLargestLevelSum(root: TreeNode | null, k: number): number {
    if (!root) return -1
    const sums: number[] = []
    const queue = [root]
    while (queue.length) {
        const len = queue.length
        let sum = 0
        for (let i = 0; i < len; i++) {
            const node = queue.shift()
            if (node) {
                sum += node.val
                if (node.left) queue.push(node.left)
                if (node.right) queue.push(node.right)
            }
        }
        sums.push(sum)
    }
    return sums.sort((a, b) => b - a)[k - 1] ?? -1
}
